\section{Cover Time for Grids} 
\label{grid}

To show a cover time bound for the $d$-dimensional grid (where each dimension of the grid is of length $n^{1/d}$), we also apply 
the technique of finding the maximum of the expected hitting times between any vertices $u,v \in G$ and then applying Matthew's 
bound. However, unlike the tree, we do not simply consider the pebble closest to the "target" vertex. Rather, we focus on making 
progress one dimension at a time towards the target (w.r.t. the coordinate of that dimension). Within this dimension, we do only 
follow the pebble closest to the target, and show that it is making a biased random walk towards its goal. Simultaneously, w.r.t. to 
other dimensions, it is making an unbiased random walk and thus remains close to its starting position in that coordinate. 
Repeating this $\log \log n$ times for each dimension, we show that it takes $O(n^{1/d} \log^c n)$ time in expectation for a cobra walk 
starting at any vertex to first reach any other vertex in the grid. Applying Matthew's bound and multiplying by another factor of $\log n$ gets us coverage in $\tilde{O}(n^{1/d})$ time. 


\begin{theorem}
\label{the:grid}
Let G be a finite d-dimensional grid on $n$ nodes for some constant d, without wrap-around edges. Then the cover time of a cobra walk on $G$ is $\tilde{O}(n^{1/d})$ w.h.p for branching factor $k = 2$. 
\end{theorem}

\begin{proof}


We want to calculate how long it takes, in expectation, for a cobra walk that starts at vertex $s = (0,\dots,0)$ to 
have at least one of its pebbles reach vertex $\omega = (n^{1/d},\ldots,n^{1/d})$ Unlike in the case of the cobra walk 
on the tree, we do not focus out attention on the pebble (out of all pebbles) closest to $\omega$, since there are 
multiple paths between $s$ and $\omega$. However, we do something similar: Imagine focusing on the progress of the
cobra walk w.r.t. only one of the dimensions of the grid, say dimension $i$. As the cobra walk progresses, we look at the pebbles'
$i$-th coordinates and keep track of the pebble closest to $\omega$'s $i$-th coordinate. We call this pebble the {\em lead pebble}.
We pick the lead pebble in each step in a manner similar to how we pick it for the tree. Suppose the lead pebble is at vertex $v$ 
who's $i$-th coordinate is $y$. In the next (branching) step of the cobra walk, if at least one of the lead pebble's offspring moves to
$y+1$, we make this pebble the lead pebble. If both of the offspring pebbles move to $y-1$ (back towards $s$ w.r.t. this dimension),
then we place the leader pebble at the adjacent vertex to $v$ with the $y-1$ coordinate.  Finally, if neither one of these two 
events occur, this means both pebbles have moved laterally in the grid (and thus make no progress backwards or forwards in 
the $i$-th coordinate). We flip a fair coin and pick one of the two pebbles as lead. It is worth pointing out for use later that 
the edge this pebble chooses to move along is chosen uniformly at random from all possible edges orthogonal to dimension $i$.

Returning to our focus on the lead pebble's progress on dimension $i$, it should be clear what we have described 
here is that our lead pebble is taking a biased random walk when we focus solely on the changes in the $i$-th coordinate (i.e.
we are projecting onto a line). It has the following transition probabilities: the probability $p_+$ of a $+1$ motion is given as
$p_+ = 1 - \left(\dfrac{2d-1}{2d}\right)^2 = \left(\dfrac{4d-1}{4d^2}\right)$, the probability $p_-$ of a $-1$ motion is $1/4d^2$, and 
the probability $p_0$ of staying in place is the remainder of the probability mass: $p_0 = \dfrac{d-1}{d}$. This projection as a 
biased random walk on the line will later allow us to use a concentration bound to calculate the probability of the walk making a 
certain amount of progress for a walk of a given length. 
 
 Although we are following the lead pebble's movement along its $i$-th coordinate, it is of course moving around the grid along its
 other coordinates. However, as noted earlier, if the lead pebble moves along an edge orthogonal to dimension $i$, that edges is 
 chosen u.a.r. from the set of all orthogonal edges. Hence, with respect to every dimension $j \neq i$, the lead pebble is making 
 a (lazy) unbiased walk. Thus, we can also use a concentration bound to show that the lead pebble's $j$-th coordinate does not
 drift very far, for all other dimensions $j$. This conveniently will allow us to focus on the lead pebble's progress
 one dimension at a time and show that it makes progress towards the target in that dimension while remaining (relatively) still
 in the other dimensions, and more importantly, not drifting very far backwards undoing any progress it might have made earlier. 
 
 More formally, we break our analysis into segments. In each segment, our goal is to have the cobra walk starting at $s$ reach $\omega$
 and do so within $O(n^{1/d})$ steps. We will show that, in any segment, this will happen with probability $q \in \Omega(1/\log^c n)$ for some
 constant $c$. We can think of each segment as being an independent trial, with probability $q$ of success. Thus, in expectation, 
 after $O(\log^c n)$ trials one success will have occurred. This gives us a maximum hitting time of a cobra walk of $O(n^{1/d} \log^c n)$. 
 Applying Matthews' bound gives us a cover time of $O(n^{1/d}\log^{c+1} n) = \tilde{O}(n^{1/d})$ for the $d$-grid.
 
 We now describe what happens in a segment. Each segment is divided into a number of phases. The first phase is of length $O(d n^{1/d})$,
 the second phase $O(d n^{1/2d})$, and in general the $i$-th phase is of length $O(d n^{1/d2^{i-1}})$. All phases have identical structure
 (except for their duration), except for the last phase, which is treated separately and is of constant duration. Within each phase,
 there are $d$ sub-phases, one for each dimension of the grid. So for some phase $M$ of length $O(d D)$ (where $D = n^{1/d2^{i-1}}$, for the $i$th phase), label the sub-phases
 $M_1,M_2,\ldots,M_d$. In sub-phase $M_i$, we allow the lead pebble selection to be governed  by the rules of advancement
 for dimension $i$ as described earlier. For the other $d-1$ sub-phases, when the lead pebble selection is governed by a 
 dimension other than $i$, the lead pebble's $i$-th coordinate is taking an unbiased random walk. 
 
 %Gopal: Where is D defined? I have changed it above.
 
 We now directly bound the probability $p_1$, that for each sub-phase $M_i$ of duration $O(d D)$ the lead pebble moves 
 toward $\omega$ in the $i$-th coordinate by at least $D - 10d\sqrt{D}/2$, and $p_2$, the probability that for the other $d-1$ sub-phases
 the lead pebble's $i$-th coordinate does not drift by more than $\sqrt{D}/2$ steps. 
 
 %Gopal --- Above, I changed it to D- 10d\sqrt{D}/2
 
 \noindent \textbf{Bound for $p_1$}.
  Let the sub-phase $M_i$ last for $K$ independent random walk steps. Let the result of each step $t$
 be a random variable $X_t$ that takes on value $1$ if a forward step is made, $-1$ if a backward step is made, and $0$ if it stays
 in place. Then $\prob{X_t = 1} = p_+$, $\prob{X_t = -1} = p_-$, and $\prob{X_t = 0} = p_0$ as defined earlier. Let $X = \sum_{t=1}^K X_t$. 
 Since $X_t \geq -1$ we can use the following version of the Chernoff bound (see Theorems 2.8 and 2.9 in ~
\cite{chung2006complex}) : 
\begin{equation} 
\prob{X  \leq E[X] - \lambda} \leq e^{\frac{-\lambda^2}{2(||X||^2 + \lambda/3)}} 
\end{equation} 
where $||X|| = \sqrt{\sum_{t=1}^K E[X_t^2]}$. It is easy to verify that $E[X_t^2] = 1/d$ and that $E[X_t] = (2d-1)/2d^2$. We
want to make expected progress of $D$ steps in the $i$-th coordinate. Setting $E[X] = D$ requires $K = \dfrac{2d^2}{2d-1} D$. Note that $|| X ||^2 = K/d$.  %Gopal --- I guess the index i should be t. I changed it.
To achieve our desired bound we set $\lambda = 10d\sqrt{D}/2$. Thus: 
\begin{eqnarray*}
\prob{X \leq E[X] - 10d\sqrt{D}/2} &\leq& e^{\dfrac{-100d^2D}{8(K/d + \sqrt{D}/6)}} \\
&=& e^{\dfrac{-600d^2D}{48K  + 8d\sqrt{D}}} \\
&=& e^{\dfrac{-600d^2D}{48 D 2d^2/(2d-1) + 8d\sqrt{D}}} \\
&=& e^{\dfrac{-600dD}{96dD/(2d-1) + 8\sqrt{D}}} \\
&\leq& e^{-4d} = 1-p_1
\end{eqnarray*} 

\noindent \textbf{Bound for $p_2$}.
 Recall that in sub phase $M_i$, the lead pebble is taking an unbiased lazy random walk w.r.t. to all other coordinates
besides $i$. Rather than calculate the exact probabilities of $+1, -1, 0$ movements of the walk when projected onto dimension $j$,
we note that such a lazy unbiased walk is stochastically dominated by an unbiased, non-lazy random walk. Thus we will calculate 
a concentration bound on this walk instead. 

Let $X_t$ take on the value $1$ if a $+1$ step is made at time $t$, and value $-1$ if a step is made in the opposite direction. Then, we analyze this walk
over $(d-1)K = (d-1)2d^2/(2d-1) \cdot D$ steps, and we would like to show that :
\begin{equation*}
\prob{X \leq E[X] - 10d^{1.5}\sqrt{D}/2} \leq (1-p_2).
\end{equation*}
  Here of course $X = \sum_{t=1}^{(d-1)K} X_t$. Thus $E[X] = 0$, $E[X_t^2] = 1$, and $||X||^2 = (d-1)\dfrac{2d^2}{(2d-1)}D$. 
 Then we can calculate:
 \begin{eqnarray*}
 \prob{X \leq -10d^3\sqrt{D}/2} &\leq& e^{\dfrac{-100d^3D}{8\left(\dfrac{(d-1)2d^2}{(2d-1)}D + \dfrac{\sqrt{D}}{6}\right)}}  \\
 &\leq& e^{\dfrac{-100d^3}{8\left(\dfrac{(d-1)2d^2}{(2d-1)} + \dfrac{1}{6}\right)}} \leq e^{-4d} = (1 - p_2). 
 \end{eqnarray*}
 %where $p_2$ is a constant independent of $D$ and $d$. 
 %Gopal --- In the above probability, the numerator in the exponent should be -D right, not -\sqrt{D}, right? I changed it.
 
 
 Thus, during phase $M$, the probability that the lead pebble's $i$-th coordinate moves ``right" by at least $D- O(\sqrt{D})$ steps
 is lower bounded (via union bound) by $p_1 + p_2 \geq 1 - 2e^{-4d}$. The probability that this happens for all dimensions is lower bounded   (via union bound over all dimensions) by $1- 2de^{-4d} = \Theta(1)$. 
 Recall that each phase runs for a length that is the square root of the phase before it. By these calculations, with each phase we grow
 progressively closer (within another square root factor) to $\omega$ with some constant probability. Indeed, after $O(\log\log n)$ phases
 we will be within a constant distance from $\omega$ in each coordinate dimension, with probability at least $(\Theta(1))^{d\log \log n}$. If we come within a constant distance, then for the last phase with some constant probability
 the remaining distance will be covered in a constant number of steps, and the lead pebble will arrive at $\omega$. Thus each phase
 succeeds with probability in $\Omega(1/\log^{\Theta(1)} n)$, and the result follows.
 
 % Gopal --- I rewrote some of the calculations above.
 
 \end{proof} 
 
 
For the special case where $d = 1$ (i.e. the line), we note that the expected cover time is $O(n)$, since by starting the cobra-walk 
at $0$ and only keeping track of the pebble closest to vertex $n$, we have a biased random walk with probability  $3/4$ of advancing 
towards $n$. This will reach $n$ in a linear number of steps. Repeating $\log n$ times would give us a high-probability 
bound.

